class Solution(object):
    def canJump(self, nums):
        """
        方法：贪心 - 正向查找
        
        逻辑：从左向右遍历数组，维护一个变量last表示能够到达的最远位置。
             对于每个位置i，如果i大于last说明无法到达该位置，返回False。
             否则更新last为max(last, i + nums[i])，表示从当前位置能跳到的最远距离。
             如果last大于等于数组最后一个位置，说明可以到达终点，返回True。
        
        Args:
            nums: List[int], 非负整数数组，表示在每个位置可以跳跃的最大长度
            
        Returns:
            bool: 是否能够到达最后一个位置
            
        Time: O(n), 其中n为数组长度
        
        Space: O(1), 只使用常数额外空间
        """
        last = 0
        for i,jump in enumerate(nums):
            if i > last:  #无法到达
                return False
            last = max(last, i + jump)
            if last >= len(nums) - 1:
                return True
            
    def canJumpLast(self, nums):
        """
        方法：贪心 - 反向查找
        
        逻辑：从右向左遍历数组，维护变量last表示需要到达的位置。
             对于每个位置i，如果从i能够跳到last(i + nums[i] >= last)，
             则更新last为i，表示现在只需要到达位置i即可。
             最后判断last是否为0，如果是0说明可以从起点到达终点。
        
        Args:
            nums: List[int], 非负整数数组，表示在每个位置可以跳跃的最大长度
            
        Returns:
            bool: 是否能够到达最后一个位置
            
        Time: O(n), 其中n为数组长度
        
        Space: O(1), 只使用常数额外空间
        """
        last = len(nums) - 1
        # 从倒数第二个位置向前遍历到第一个位置
        # range(start, stop, step) 生成一个序列:
        # - 从 len(nums)-2 开始(倒数第二个位置)
        # - 到 -1 结束(不包含-1,即到达索引0)  
        # - 步长为 -1(从后向前遍历)
        for i in range(len(nums) - 2, -1, -1):
            if i + nums[i] >= last:
                last = i
        return last == 0        